//package com.gitee.feizns.explore.data_structure.tree.cus.rbt;
//
//import java.util.Collection;
//import java.util.Set;
//import java.util.TreeSet;
//import java.util.stream.Collectors;
//
///**
// * @author feizns
// * @since 2020/1/2
// */
//public class Rbt4<K extends Comparable<K>, V> implements Rbt<Rbt4.Node, K, V> {
//
//    public static void main(String[] args) {
//        Rbt4 rbt = new Rbt4();
//        rbt.put(1, "1");
//        rbt.put(2, "2");
//        rbt.put(3, "3");
//        rbt.put(4, "4");
//        rbt.put(5, "5");
//        rbt.put(6, "5");
//        rbt.put(7, "5");
//        rbt.put(8, "5");
//        rbt.put(9, "5");
//        rbt.put(10, "5");
//
//        System.out.println(rbt.get(5));
//
//        rbt.remove(5);
//        rbt.remove(4);
//        rbt.remove(3);
//        rbt.remove(2);
//        rbt.remove(1);
//        rbt.remove(10);
//        rbt.remove(9);
//        rbt.remove(8);
//        rbt.remove(7);
//        rbt.remove(6);
//
//    }
//
//    private Node<K, V> root;
//
//    private int size;
//
//    @Override
//    public com.gitee.feizns.explore.data_structure.tree.cus.Node root() {
//        return root;
//    }
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public V get(Object key) {
//        Node<K, V> tmp;
//        return (tmp = find(root, (K) key)) != null ? tmp.v : null;
//    }
//
//    private Node find(Node node, K k) {
//        if ( node != null ) {
//            int comp = k.compareTo((K) node.k);
//            if ( comp < 0 )
//                return find(node.left, k);
//            else if ( comp > 0 )
//                return find(node.right, k);
//            else
//                return node;
//        }
//        return null;
//    }
//
//    @Override
//    public V put(K key, V value) {
//        NAndV ret = put(root, key, value);
//        root = ret.n;
//        toBlank(root);
//        return ret.v;
//    }
//
//    private NAndV put(Node node, K k, V v) {
//        if ( node == null ) {
//            size++;
//            return new NAndV(new Node<>(k, v), null);
//        }
//
//        V retV;
//        int comp = k.compareTo((K) node.k);
//        if ( comp < 0 ) {
//            NAndV ret = put(node.left, k, v);
//            node.left = ret.n;
//            retV = ret.v;
//        } else if ( comp > 0 ) {
//            NAndV ret = put(node.right, k, v);
//            node.right = ret.n;
//            retV = ret.v;
//        } else {
//            retV = (V) node.v;
//            node.v = v;
//        }
//
//        node = balance(node);
//        return new NAndV(node, retV);
//    }
//
//    private Node balance(Node node) {
//        if ( node != null ) {
//            if ( !isRed(node) && isRed(node.right) )
//                node = leftRotate(node);
//            if ( isRed(node.left) && isRed(node.left.left) )
//                node = rightRotate(node);
//            if ( isRed(node.left) && isRed(node.right) ) {
//                toRed(node);
//                toBlank(node.left);
//                toBlank(node.right);
//            }
//        }
//        return node;
//    }
//
//    private static Node leftRotate(Node node) {
//        Node right = node.right;
//        node.right = right.left;
//        right.left = node;
//        right.color = node.color;
//        node.color = RED;
//        return right;
//    }
//
//    private static Node rightRotate(Node node) {
//        Node left = node.left;
//        node.left = left.right;
//        left.right = node;
//        left.color = node.color;
//        node.color = RED;
//        return left;
//    }
//
//    private static void toRed(Node node) {
//        if ( node != null )
//            node.color = RED;
//    }
//    private static void toBlank(Node node) {
//        if ( node != null )
//            node.color = BLANK;
//    }
//
//    private static boolean isRed(Node node) {
//        return node != null && node.color == RED;
//    }
//
//    @Override
//    public V remove(Object key) {
//        NAndV nAndV = remove(root, (K) key);
//        root = nAndV.n;
//        toBlank(root);
//        return nAndV.v;
//    }
//
//    private NAndV remove(Node node, K k) {
//        if ( node != null ) {
//            V v;
//            int comp = k.compareTo((K) node.k);
//            if ( comp < 0 ) {
//                node = moveToLeft(node);
//                NAndV nAndV = remove(node.left, k);
//                node.left = nAndV.n;
//                v = nAndV.v;
//            } else if ( comp > 0 ) {
//                node = moveToRight(node);
//                NAndV nAndV = remove(node.right, k);
//                node.right = nAndV.n;
//                v = nAndV.v;
//            } else {
//                v = (V) node.v;
//                if ( node.left == null && node.right == null ) {
//                    size--;
//                    return new NAndV(null, v);
//                } else if ( node.left != null ) {
//                    Node max = max(node.left);
//                    node.k = max.k;
//                    node.v = max.v;
//                    node = moveToLeft(node);
//                    NAndV nAndV = remove(node.left, (K) max.k);
//                    node.left = nAndV.n;
//                } else {
//                    Node min = min(node.right);
//                    node.k = min.k;
//                    node.v = min.v;
//                    node = moveToRight(node);
//                    NAndV nAndV = remove(node.right, (K) min.k);
//                    node.right = nAndV.n;
//                }
//            }
//            return new NAndV(balance(node), v);
//        }
//        return new NAndV();
//    }
//
//    private static Node min(Node node) {
//        return node.left != null ? min(node.left) : node;
//    }
//
//    private static Node max(Node node) {
//        return node.right != null ? max(node.right) : node;
//    }
//
//    private static Node moveToLeft(Node node) {
//        if ( node.left != null ) {
//            if ( !isRed(node.left) && !isRed(node.left.left) && !isRed(node.left.right) ) {
//                if ( node.right != null ) {
//                    if ( !isRed(node.right.left) && !isRed(node.right.right) ) {
//                        toBlank(node);
//                        toRed(node.left);
//                        toRed(node.right);
//                    } else {
//                        if ( isRed(node.right.left) )
//                            node.right = rightRotate(node.right);
//                        node = leftRotate(node);
//                        toBlank(node.left);
//                        toRed(node.left.left);
//                        toRed(node.left.right);
//                    }
//                }
//            }
//        }
//        return node;
//    }
//
//    private static Node moveToRight(Node node) {
//        if ( node.right != null ) {
//            if ( !isRed(node.right) && !isRed(node.right.left) && !isRed(node.right.right) ) {
//                if ( node.left != null ) {
//                    if ( !isRed(node.left.left) && !isRed(node.left.right) ) {
//                        toBlank(node);
//                        toRed(node.left);
//                        toRed(node.right);
//                    } else {
//                        if ( isRed(node.left.right) )
//                            node.left = leftRotate(node.left);
//                        node = rightRotate(node);
//                        toBlank(node.right);
//                        toRed(node.right.left);
//                        toRed(node.right.right);
//                    }
//                }
//            }
//        }
//        return node;
//    }
//
//    @Override
//    public void clear() {
//        root = null;
//        size = 0;
//    }
//
//    @Override
//    public Set<K> keySet() {
//        return entrySet().stream().map(Entry::getKey).collect(Collectors.toSet());
//    }
//
//    @Override
//    public Collection<V> values() {
//        return entrySet().stream().map(Entry::getValue).collect(Collectors.toList());
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        Set<Entry<K, V>> entries = new TreeSet<>();
//        middleEach((k, v) -> entries.add(new EntryImpl(k, v)));
//        return entries;
//    }
//
//    class NAndV {
//        Node<K, V> n;
//        V v;
//        public NAndV(Node<K, V> n, V v) {
//            this.n = n;
//            this.v = v;
//        }
//        public NAndV() {}
//    }
//
//    static final boolean RED = false;
//    static final boolean BLANK = true;
//    static class Node<K extends Comparable<K>, V> implements com.gitee.feizns.explore.data_structure.tree.cus.Node<Node, K, V> {
//        K k;
//        V v;
//        boolean color;
//        Node left, right;
//        public Node(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//        public Node(K k, V v, boolean color) {
//            this.k = k;
//            this.v = v;
//            this.color = color;
//        }
//        @Override
//        public K key() {
//            return k;
//        }
//
//        @Override
//        public void key(K k) {
//            this.k = k;
//        }
//
//        @Override
//        public V val() {
//            return v;
//        }
//
//        @Override
//        public void val(V v) {
//            this.v = v;
//        }
//
//        @Override
//        public Node left() {
//            return left;
//        }
//
//        @Override
//        public void left(Node left) {
//            this.left = left;
//        }
//
//        @Override
//        public Node right() {
//            return right;
//        }
//
//        @Override
//        public void right(Node right) {
//            this.right = right;
//        }
//    }
//
//    public static class EntryImpl<K, V> implements Entry<K, V> {
//        K k;
//        V v;
//        public EntryImpl(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//        @Override
//        public K getKey() {
//            return k;
//        }
//
//        @Override
//        public V getValue() {
//            return v;
//        }
//
//        @Override
//        public V setValue(V value) {
//            V old = v;
//            v = value;
//            return old;
//        }
//    }
//
//}
